%[elements,found,main] = search(main,pos,marker,first)
%   This function is actually a recursive search algorithm. It is not
%   purely recursive, but it searches parts per iteration via a loop. 
%   It searches the complementary marker with the same value as the
%   inputted 'marker' and the elements of the ring ('elements') from
%   position 'pos' within struct 'main'. The first iteration of the
%   function has to be given the value 'true' for the input 'first'. It
%   returns it's findings in the array 'elements' and signals it's find by
%   returning the value 'true' within 'found'. The struct 'main' is also
%   retruned, possibly altered to fit future use.

%%

function [elements,found,main] = search(main,pos,marker,first)

%% Initialising
%The ringmarker has not been found yet:
found = false;
%Current array 'elements' is empty:
elements = [];

%Make sure all elements in the field 'ringmarker' are 0 instead of empty
%when unassigned.
if length(main) ~= length([main.ringmarker])
    for j = 1:length(main)
        if isempty(main(j).ringmarker)
            main(j).ringmarker = 0;
        end
    end
end

%If this is the first iteration:
if first
    firstpos = pos;
else
    firstpos = 0;
end

%Make sure the field 'search' exists
if ~myIsField(main,'search')
    main(pos).search = [];
end

%Making sure the fields that are called upon exist
if ~myIsField(main,'hasBranch')
    main(1).hasBranch = [];
end


%% Main

%elements that are in the same branch as 'pos'
a = find([main.branch] == main(pos).branch);
%elements in this branch from 'pos' to end.
b = a(a>=pos);

%For all elements in the current branch that come after 'pos'
stepsize = 0;
while ~found && stepsize < length(b)
    stepsize = stepsize+1;
    j = b(stepsize); %'j' is the index
    elements = [elements j];
    %If the current position has a branch, start this program for every
    %branch while the marker has not been found.
    if ~isempty(main(j).hasBranch)
        count = 0;
        while ~found && count < length(main(j).hasBranch)
            count = count+1;
            if isempty(main(main(j).hasBranch(count)).search)
                main(main(j).hasBranch(count)).search = 1;
                [elements2,found,main] = search(main,main(j).hasBranch(count),marker,false);
            end
        end
    end
    %If the marker has been found in a branch, add the branch to the elements
    %of the ring.
    if found
        elements = [elements elements2];
    end
    elements2 = [];
    %Check whether the current has the correct ringmarker.
    if sum(main(j).ringmarker == marker) && firstpos ~= j
        found = true;
    end
end

%If the ringmarker hasn't been found in this branch:
if ~found
    %If we can step back a branch:
    if main(pos).branch > 0
        %All atoms from 'pos' to the beginning of the branch now are
        %elements
        if first == 1
            elements = sort([a(a<=pos)],'descend');
        else
            elements = [];
        end
        %Search the branch a step back:
        main(a(1)).search = 1; %Label current branch as searched.
        [elements2,found,main] = search(main,main(pos).branchorigin,marker,false);
        %If found, add those elements, else report an error.
        if found
            elements = [elements elements2];
            if main(j).branch > 0
                elements2 = [];
            end
        else
            if sum(main.ringmarker == marker) ~= 2
                error(['An unmatched ringmarker has been detected, the input'...
                    ' is invalid. Please check the input for unpaired '...
                    'marked ringatoms. The number that was unmatched was: '...
                    num2str(marker) '.'])
            else
                error(['The program has run into an unexpected error: '...
                    'A ringmarker could not be paired by the search '...
                    'algorithm. The ringmarker posing the problem was: '...
                    num2str(marker) ' on atom number ' num2str(pos) '.'])
            end
        end
        %If not found, display error.
    else
        if sum(main.ringmarker == marker) ~= 2
            error(['An unmatched ringmarker has been detected, the input'...
                ' is invalid. Please check the input for unpaired '...
                'marked ringatoms. The number that was unmatched was: '...
                num2str(marker) '.'])
        else
            error(['The program has run into an unexpected error: '...
                'A ringmarker could not be paired by the search '...
                'algorithm. The ringmarker posing the problem was: '...
                num2str(marker) ' on atom number ' num2str(pos) '.'])
        end
    end
end

%Remove double elements from the array 'elements'.
j = 1;
while j <= length(elements)-1
    if elements(j) == elements(j+1)
        elements(j+1) = [];
    else
        j = j+1;
    end
end

%% End
end